package com.yulongtian.oneProblemEveryDay.month202302;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode.cn/problems/maximum-score-words-formed-by-letters/@author yulongTian
 * 可
 *
 * @create 2023-02-26 9:34
 */
public class Test21 {
    public static void main(String[] args) {
        String[] words = {"dog", "cat", "dad", "good"};
        char[] letters = {'a', 'a', 'c', 'd', 'd', 'd', 'g', 'o', 'o'};
        int[] score = {1, 0, 9, 5, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        System.out.println(new Test21().maxScoreWords(words, letters, score));
    }

    //暴力所有非空集合组合

    /**
     * words.length最多14，words内各单词全组合最多2**14种情况，直接考虑暴力遍历全组合计算。
     * <p>
     * 步骤：遍历每种组合，对组合内单词的每个字符计数，
     * 若计数满足letters字母数额度内则计算该组合的得分，判断保留最大值返回。
     * <p>
     */
    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int[] cnt = new int[26];
        for (char c : letters) {
            cnt[c - 'a']++;
        }
        int[] ans = new int[1];
        Stack<String> stack = new Stack<>();
        dfs(0, stack, words, cnt, score, ans);
        return ans[0];
    }

    public void dfs(int start, Stack<String> stack, String[] words, int[] letters, int[] score, int[] ans) {
        if (start >= words.length) {
            return;
        }
        for (int i = start; i < words.length; i++) {
            stack.push(words[i]);
            int temp_score = check(stack, letters, score);
            if (temp_score != -1) {
                ans[0] = Math.max(ans[0], temp_score);
            }
            dfs(i + 1, stack, words, letters, score, ans);
            stack.pop();
        }
    }

    //判断是否符合个数条件
    public int check(Stack<String> stack, int[] letters, int[] score) {
        List<String> temp_list = new ArrayList<>(stack);
        int[] cnt = new int[26];
        int ans = 0;
        for (String s : temp_list) {
            for (int i = 0; i < s.length(); i++) {
                int a = s.charAt(i) - 'a';
                cnt[a]++;
                ans += score[a];
                if (cnt[a] > letters[a]) {
                    return -1;
                }
            }
        }
        return ans;
    }


}
